import random

'''
方法一 直接利用列表进行递归
'''
def quick_sort1(li):
    if len(li) < 2:
        return li
    tmp = li[0]
    left = [v for v in li[1:] if v <= tmp]
    right = [v for v in li[1:] if v > tmp]
    left = quick_sort1(left)
    right = quick_sort1(right)
    return left + [tmp] + right


li = list(range(1000))
random.shuffle(li)
print(quick_sort1(li))


'''
方法二 正常交换递归
'''

def quick_sort2(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quick_sort2(li, left, mid - 1)
        quick_sort2(li, mid + 1, right)


def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]
    li[left] = tmp
    return left


li = list(range(1000))
random.shuffle(li)
quick_sort2(li, left=0, right=len(li)-1)
print(li)

